#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <stack>

#define DEBUG 0 

using namespace std;

class move {
	public:
		int from;
		int over;
		int to;
		move(int f, int o, int t)
		{
			from = f;
			over = o;
			to = t;
		};
		~move() {}
		void print()
		{
			cout << from << " - " << 
				over << " - " << to << endl;
		}
};

typedef stack<move *> moves;
typedef moves solution;
typedef vector< pair<int, char> > board; // pos, frog

class puzzle {
	public:
		puzzle(char *file);
		~puzzle();
		void print_board();
		bool solve();
		void print_solution();

	private:
		board b; 
		vector<move *> movtab;
		solution s;

		void read(char *file);
		void setup_move_table();
		bool is_empty(int pos);
		char at(int pos);
		bool can_jump(char frog, int jmp_from_pos, 
				int jmp_over_pos, int jmp_to_pos);
		bool gen_moves(moves& m);
		void make_move(move& m);
		void undo_move(move& m);
		bool solved();
};

puzzle::puzzle(char *file)
{
	setup_move_table();
	read(file);
}

puzzle::~puzzle()
{
}

void puzzle::print_board()
{
	for (int i = 0; i < b.size(); i++)
		cout << b[i].first << " " << b[i].second << endl;
}

bool puzzle::solve()
{
	moves m;

	if (solved())
		return true;

	// Generate candidate moves 
	if (!gen_moves(m))
		return false;

	// Recursively (depth-first) try out candidate moves
	while (m.size() != 0) {
		move mov(m.top()->from, 
				m.top()->over, 
				m.top()->to);
		m.pop();
		make_move(mov);
		if (solve()) {
			// Add move to solution
			s.push(new move(mov.from, mov.over, mov.to));
			return true;
		} else 
			// Backtrack
			undo_move(mov);
	}
	return false;	
}

void puzzle::print_solution()
{
	while (s.size() != 0) {
		s.top()->print();
		s.pop();
	}
}

void puzzle::read(char *file)
{
	fstream fs;
	int pos;
	char frog;

	fs.open(file, fstream::in);
	while (true)
	{
		fs >> pos >> frog;
		if (fs.eof())
			break;
		b.push_back(make_pair(pos, frog));
	}
	fs.close();

#if DEBUG	
	print_board();
#endif	
}

void puzzle::setup_move_table()
{
	movtab.push_back(new move(1, 2, 3));
	movtab.push_back(new move(1, 4, 7));
	movtab.push_back(new move(1, 6, 11));
	movtab.push_back(new move(2, 4, 6));
	movtab.push_back(new move(2, 7, 12));
	movtab.push_back(new move(2, 5, 8));
	movtab.push_back(new move(3, 2, 1));
	movtab.push_back(new move(3, 5, 7));
	movtab.push_back(new move(3, 8, 13));
	movtab.push_back(new move(4, 7, 10));
	movtab.push_back(new move(5, 7, 9));
	movtab.push_back(new move(6, 4, 2));
	movtab.push_back(new move(6, 7, 8));
	movtab.push_back(new move(6, 9, 12));
	movtab.push_back(new move(7, 4, 1));
	movtab.push_back(new move(7, 5, 3));
	movtab.push_back(new move(7, 9, 11));
	movtab.push_back(new move(7, 10, 13));
	movtab.push_back(new move(8, 5, 2));
	movtab.push_back(new move(8, 7, 6));
	movtab.push_back(new move(8, 10, 12));
	movtab.push_back(new move(9, 7, 5));
	movtab.push_back(new move(10, 7, 4));
	movtab.push_back(new move(11, 6, 1));
	movtab.push_back(new move(11, 9, 7));
	movtab.push_back(new move(11, 12, 13));
	movtab.push_back(new move(12, 9, 6));
	movtab.push_back(new move(12, 7, 2));
	movtab.push_back(new move(12, 10, 8));
	movtab.push_back(new move(13, 12, 11));
	movtab.push_back(new move(13, 10, 7));
	movtab.push_back(new move(13, 8, 3));
}

bool puzzle::is_empty(int pos)
{
	for (int i = 0; i < b.size(); i++)
		if (b[i].first == pos)
			return false;
	return true;
}

char puzzle::at(int pos)
{
	for (int i = 0; i < b.size(); i++)
		if (b[i].first == pos)
			return b[i].second;
}

bool puzzle::can_jump(char frog, int jmp_from_pos, 
		int jmp_over_pos, int jmp_to_pos)
{
	if (!is_empty(jmp_to_pos)) 
		return false;
	if (is_empty(jmp_over_pos))
		return false;
	if (frog == 'G' && at(jmp_over_pos) == 'R')
		return false;
	return true;
}

bool puzzle::gen_moves(moves& m)
{
	bool found = false;

	for (int i = 0; i < b.size(); i++) {
		int jmp_from_pos = b[i].first;
		char frog = b[i].second;
		for (int j = 0; j < movtab.size(); j++) {
			if (movtab[j]->from != jmp_from_pos)
				continue;
			int jmp_over_pos = movtab[j]->over;
			int jmp_to_pos = movtab[j]->to;
			if (can_jump(frog, 
						jmp_from_pos, 
						jmp_over_pos, 
						jmp_to_pos)) {
				found = true;
				m.push(new move(jmp_from_pos, 
							jmp_over_pos, jmp_to_pos));
			}
		}
	}
	return found;	
}

void puzzle::make_move(move& m)
{
	board::iterator i, j;
	for (i = b.begin(); i != b.end(); i++) {
		if (m.from == (*i).first) {
			char frog = (*i).second;
			int jmp_over_pos = m.over;
			int jmp_to_pos = m.to;

			b.erase(i);
			b.push_back(make_pair(jmp_to_pos, frog));

			for (j = b.begin(); j != b.end(); j++)
				if (jmp_over_pos == (*j).first)
					b.erase(j);
			return;
		}	
	}
	return;
}

void puzzle::undo_move(move& m)
{
	board::iterator i, j;

	int jmp_to_pos = m.to;
	int jmp_over_pos = m.over;
	int jmp_from_pos = m.from;
	char frog;

	for (i = b.begin(); i != b.end(); i++) {
		if (jmp_to_pos == (*i).first) {
			frog = (*i).second;
			b.erase(i);
			b.push_back(make_pair(jmp_over_pos, 'G'));
			b.push_back(make_pair(jmp_from_pos, frog));
			return;
		}
	}

}

bool puzzle::solved()
{
	return b.size() == 1;
}

int main(int argc, char *argv[])
{

	if (argc < 2) {
		cout << "Usage: hoppers_solver <puzzle_file>" << endl;
		return 1;
	}

	puzzle p(argv[1]);
	if (p.solve()) {
		cout << "Solution: " << endl;
		p.print_solution();
	} else
		cout << "Puzzle has no solution." << endl;

	return 0;
}
